#ifndef GAME_ANIMATION_GRID_CELL_SORTING_H
#define GAME_ANIMATION_GRID_CELL_SORTING_H
//
// Game Animation.
// Copyright (C) 2007 Department of Computer Science, University of Copenhagen
//
#include <animation/configuration.h>

#include <vector>
#include <cassert>
#include <boost/iterator/indirect_iterator.hpp>

namespace animation
{


  /**
   * Cell Sorting Algorithm.
   * This class provides functionality to depth sort grid cells. This is useful
   * during rendering. For instance to handle transparency, depth culling, and
   * occlusion queries more efficiently.
   */
  template<typename types>
  class CellSorting
  {
  public:

    typedef typename types::cell_type                 cell_type;
    typedef typename types::grid_type                 grid_type;
    typedef typename std::vector<cell_type *>         cell_ptr_array;

    typedef typename cell_ptr_array::iterator                                  cell_ptr_iterator;
    typedef typename cell_ptr_array::const_iterator                            const_cell_ptr_iterator;
    typedef boost::indirect_iterator<cell_ptr_iterator,cell_type>              cell_iterator;
    typedef boost::indirect_iterator<const_cell_ptr_iterator,cell_type const>  const_cell_iterator;

    typedef typename cell_ptr_array::reverse_iterator                                  cell_ptr_reverse_iterator;
    typedef typename cell_ptr_array::const_reverse_iterator                            const_cell_ptr_reverse_iterator;
    typedef boost::indirect_iterator<cell_ptr_reverse_iterator,cell_type>              cell_reverse_iterator;
    typedef boost::indirect_iterator<const_cell_ptr_reverse_iterator,cell_type const>  const_cell_reverse_iterator;

  protected:

    struct depth_sorting
    {
      bool operator()(cell_type * x,cell_type * y)
      {
        return (x->depth() > y->depth()); ///--- using '>' gives back to front order!!!
      }
    };

    cell_ptr_array   m_cell_ptrs;   ///< Pointers to all cells stored in a virtual grid.

  public:

    cell_iterator  begin() {  return m_cell_ptrs.begin(); }
    cell_iterator  end()   {  return m_cell_ptrs.end();   }
    const_cell_iterator  begin()const {  return m_cell_ptrs.begin(); }
    const_cell_iterator  end()  const {  return m_cell_ptrs.end();   }

    cell_reverse_iterator  rbegin() {  return m_cell_ptrs.rbegin(); }
    cell_reverse_iterator  rend()   {  return m_cell_ptrs.rend();   }
    const_cell_reverse_iterator  rbegin()const {  return m_cell_ptrs.rbegin(); }
    const_cell_reverse_iterator  rend()  const {  return m_cell_ptrs.rend();   }

	int size(){return m_cell_ptrs.size();}
  public:

    /**
    * Initialize internal data structures.
    *
    * @param grid        The grid containing the cells that should be depth sorted.
    */
    void init(grid_type & grid)
    {
      m_cell_ptrs.resize(grid.size());
      unsigned int i=0;
      for( typename grid_type::cell_iterator cell = grid.begin();cell!=grid.end();++cell,++i)
        m_cell_ptrs[i] = &(*cell);
    }

    /**
    * Sort Cells.
    * Upon completion one can use the begin() and end() methods to access
    * the cells in their sorted order.
    *
    * @param camera    The camera wrt. which the sorting should be done.
    */
    template<typename camera_type>
    void sort(camera_type const & camera)
    {
      for(cell_iterator cell = begin();cell!=end();++cell)
        cell->depth() = camera.depth(cell->get_center());
      std::sort(m_cell_ptrs.begin(), m_cell_ptrs.end(), depth_sorting() );
    }
  };

} // namespace animation

// GAME_ANIMATION_GRID_CELL_SORTING_H
#endif
